% re-flex.tex

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.40\textwidth}{figs/flex}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 输入:} 程序文本/字符串 $s$ \& 词法单元的规约

    \vspace{0.50cm}
    \fig{width = 0.50\textwidth}{figs/lexer}

    \vspace{0.30cm}
    \red{\bf 输出:} 词法单元流
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 输入:} 词法单元的规约

    \vspace{0.50cm}
    \fig{width = 0.50\textwidth}{figs/flex-flow}

    \vspace{0.30cm}
    \red{\bf 输出:} 词法分析器
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    词法单元的规约

    \vspace{0.40cm}
    \begin{columns}
      \column{0.30\textwidth}
        \uncover<2->{\fig{width = 0.70\textwidth}{figs/do-not-understand}}
      \column{0.70\textwidth}
        \fig{width = 1.00\textwidth}{figs/token-table}
    \end{columns}

    \pause
    \vspace{0.60cm}
    我们需要词法单元的\red{\bf 形式化}规约
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \id: 字母开头的字母/数字串

    \vspace{0.80cm}
    \id{} 定义了一个集合, 我们称之为\red{\bf 语言 (Language)} \\[15pt]
    它使用了字母与数字等符号集合, 我们称之为\blue{\bf 字母表 (Alphabet)} \\[15pt]
    该语言中的每个元素(即, 标识符)称为\purple{\bf 串 (String)}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[字母表]
    字母表 $\Sigma$ 是一个有限的符号集合。
  \end{definition}
  
  \fig{width = 0.35\textwidth}{figs/symbols}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[串]
    字母表 $\Sigma$ 上的串 ($s$) 是由 $\Sigma$ 中符号构成的一个{\bf 有穷}序列。
  \end{definition}

  \fig{width = 0.30\textwidth}{figs/epsilon}
  \vspace{-0.30cm}
  \[
    \text{空串}: |\epsilon| = 0
  \]
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[串上的``连接''运算]
    \[
      x = dog, y = house \qquad xy = doghouse
    \]

    \[
      s \epsilon = \epsilon s = s
    \]
  \end{definition}

  \pause
  \vspace{0.60cm}
  \begin{definition}[串上的``指数''运算]
    \[
      s^{0} \triangleq \epsilon
    \]

    \[
      s^{i} \triangleq s s^{i-1}, i > 0
    \]
  \end{definition}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[语言]
    语言是给定字母表 $\Sigma$ 上一个任意的{\bf 可数的}串集合。
  \end{definition}

  \[
    \emptyset \qquad \set{\epsilon}
  \]

  \pause
  \[
    \id: \set{a, b, c, a1, a2, \dots}
  \]

  \[
    \ws: \set{\blank, \tab, \line}
  \]

  \[
    \ifkw: \set{if}
  \]
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\Large \bf 语言是串的集合}

    \vspace{0.80cm}
    因此, 我们可以通过集合操作{\bf 构造}新的语言。
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{columns}
    \column{0.75\textwidth}
      \fig{width = 1.00\textwidth}{figs/language-operator}

      \begin{center}
        $L^{\ast}$ 允许我们构造{\bf 无穷}集合
      \end{center}
    \column{0.25\textwidth}
      \fig{width = 1.00\textwidth}{figs/kleene}
      \begin{center}
        Stephen Kleene (1909 $\sim$ 1994)
      \end{center}
  \end{columns}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \[
    L = \set{A, B, \dots, Z, a, b, \dots, z}
  \]
  \[
    D = \set{0, 1, \dots, 9}
  \]
  \fig{width = 0.70\textwidth}{figs/language-operator}

  \pause
  \[
    L \cup D \qquad LD \qquad L^4 \qquad L^{\ast} \qquad D^{+}
  \]

  \[
    \red{L(L \cup D)^{\ast}}
  \]
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \[
    \id: \red{L(L \cup D)^{\ast}}
  \]
  
  \begin{center}
    如何更简洁地描述该 \id{} 语言?
  \end{center}

  \pause
  \fig{width = 0.50\textwidth}{figs/regex}
  \begin{center}
    下面向大家隆重介绍简洁、优雅、强大的\red{\bf 正则表达式}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    每个正则表达式 $r$ 对应一个正则语言 $L(r)$

    \vspace{0.30cm}
    \fig{width = 0.50\textwidth}{figs/syntax-semantics}

    \vspace{0.30cm}
    正则表达式是\red{\bf 语法}, 正则语言是\red{\bf 语义}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{definition}[正则表达式]
    给定字母表 $\Sigma$, $\Sigma$ 上的正则表达式\red{\bf 由且仅由}以下规则定义:
    \begin{enumerate}[(1)]
      \item $\epsilon$ 是正则表达式;
      \item $\forall a \in \Sigma$, $a$ 是正则表达式;
      \item 如果 $r$ 是正则表达式, 则 $(r)$ 是正则表达式;
      \item 如果 $r$ 与 $s$ 是正则表达式, 则 $r|s$, $rs$, $r^{\ast}$ 也是正则表达式。
    \end{enumerate}

    \vspace{0.30cm}
    \begin{center}
      运算优先级: $()\; \purple{\succ} \ast\; \purple{\succ} \text{ 连接 }\; \purple{\succ}\; |$
    \end{center}
    \[
      (a) | ((b)^{\ast}(c)) \equiv a | b^{\ast} c
    \]
  \end{definition}

  \pause
  \vspace{0.30cm}
  \begin{center}
    \red{\bf 结构 (Structure)}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    每个正则表达式 $r$ 对应一个正则语言 $L(r)$
  \end{center}

  \begin{definition}[正则表达式对应的正则语言]
    \begin{gather}
      L(\epsilon) = \set{\epsilon} \\[8pt]
      L(a) = \set{a}, a \in \Sigma \\[8pt]
      L((r)) = L(r) \\[8pt]
      \red{L(r|s) = L(r) \cup L(s) \quad L(rs) = L(r)L(s) 
      \quad L(r^{\ast}) = (L(r))^{\ast}}
    \end{gather}
  \end{definition}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \[
    \Sigma = \set{a, b}
  \]

  \[
    L(a | b) = \set{a, b}
  \]

  \pause
  \[
    L((a | b) (a | b))
  \]

  \pause
  \[
    L(a^{\ast})
  \]

  \pause
  \[
    L((a | b)^{\ast})
  \]

  \pause
  \[
    L(a | a^{\ast}b)
  \]
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.50\textwidth}{figs/too-easy}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.75\textwidth}{figs/regex-extended}
  \[
    [0-9] \quad [a-zA-Z] \qquad \red{\hat\qquad \$}
  \]
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    {\bf 正则定义}与简记法
  \end{center}

  \fig{width = 0.92\textwidth}{figs/regex-shorthand}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    C 语言中的标识符?
  \end{center}

  \pause
  \fig{width = 0.60\textwidth}{figs/reg101-id}
\end{frame}{}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    整数部分$.$小数部分\texttt{E/e}指数部分
  \end{center}

  \pause
  \fig{width = 0.95\textwidth}{figs/reg101-number}
\end{frame}{}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    C 语言中{\bf 单行注释}对应的正则表达式?
  \end{center}

  \pause
  \fig{width = 0.80\textwidth}{figs/reg101-single-line-comment}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    C 语言中{\bf 多行注释}对应的正则表达式?
  \end{center}

  \pause
  \fig{width = 0.80\textwidth}{figs/reg101-multi-line-comment}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \[ 
    \Big(0|\big(1(01^{\ast}0)^{\ast}1\big)\Big)^{\ast} 
  \]
  \fig{width = 0.40\textwidth}{figs/what-is-this}

  \begin{center}
    \blue{\url{https://regex101.com/r/ED4qgC/1}}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    Flex 程序的结构 ($.l$ 文件)
  \end{center}

  \begin{columns}
    \column{0.55\textwidth}
      \begin{description}
        \setlength{\itemsep}{12pt}
        \item[声明部分:] 直接拷贝到$.c$文件中
        \item[转换规则:] \red{\bf 正则表达式 \set{动作}}
        \item[辅助函数:] 动作中使用的辅助函数
      \end{description}
    \column{0.45\textwidth}
      \fig{width = 0.40\textwidth}{figs/flex-structure}
  \end{columns}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.75\textwidth}{figs/flex-def}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.80\textwidth}{figs/flex-rule}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.80\textwidth}{figs/flex-func}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.85\textwidth}{figs/flex-wc}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    两大\red{\bf 冲突解决}规则

    \vspace{1.20cm}
    {\bf 最前优先匹配:} 关键字

    \vspace{0.60cm}
    {\bf 最长优先匹配:} ``>='', ``ifhappy''
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%